package com.cn.algorithm02.class14;

import com.cn.algorithm02.class01.Nodea;

/***
 * @author: hels
 * @description:
 * 给定一颗二叉树的头结点head
 * 返回这棵二叉树最大的二叉搜索子树的头节点
 **/
public class C02_ReturnMaxSubBSTHead {
    public static void main(String[] args) {
        int[] arr = {1, 4, 20, 1, 6, 17, 22};
        Nodea head = Nodea.getNodeInstance(arr);
        head.left.right.right = new Nodea(8);

        Nodea.printTree(head);
        System.out.println(returnHead(head));

    }

    public static Nodea returnHead(Nodea head) {
        if (head == null) return null;
        return process(head).subBSTHead;
    }

    public static Info process(Nodea x) {
        if (x == null) return null;

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int min = x.value;
        int max = x.value;
        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }
        int allSize = 1;
        allSize = isInfoNN(leftInfo) ? allSize + leftInfo.allSize : allSize;
        allSize = isInfoNN(rightInfo) ? allSize + rightInfo.allSize : allSize;
        // 最大BST的size
        // 左右子树是否为
        boolean leftBST = (!isInfoNN(leftInfo) || (leftInfo.maxSubBstSize == leftInfo.allSize)) ? true : false;
        boolean rightBST = (!isInfoNN(rightInfo) || (rightInfo.maxSubBstSize == rightInfo.allSize)) ? true : false;
        int maxSubBstSize = 0;
        Nodea subBSTHead = null;
        if (!isInfoNN(leftInfo) && !isInfoNN(rightInfo)) {
            maxSubBstSize = 1;
            subBSTHead = x;
        } else if (isInfoNN(leftInfo) && isInfoNN(rightInfo)) {
            if (leftBST && rightBST && leftInfo.max < x.value && x.value < rightInfo.min) {
                maxSubBstSize = leftInfo.maxSubBstSize + rightInfo.maxSubBstSize + 1;
                subBSTHead = x;
            } else {
                maxSubBstSize = leftInfo.maxSubBstSize >= rightInfo.maxSubBstSize ? leftInfo.maxSubBstSize : rightInfo.maxSubBstSize;
                subBSTHead = leftInfo.maxSubBstSize > rightInfo.maxSubBstSize ? leftInfo.subBSTHead : rightInfo.subBSTHead;
            }
        } else if (!isInfoNN(leftInfo) && isInfoNN(rightInfo)) {
            if (rightBST && x.value < rightInfo.min) {
                maxSubBstSize = rightInfo.maxSubBstSize + 1;
                subBSTHead = x;
            } else {
                maxSubBstSize = rightInfo.maxSubBstSize;
                subBSTHead = rightInfo.subBSTHead;
            }
        } else if (isInfoNN(leftInfo) && !isInfoNN(rightInfo)) {
            if (leftBST && x.value > leftInfo.max) {
                maxSubBstSize = leftInfo.maxSubBstSize + 1;
                subBSTHead = x;
            } else {
                maxSubBstSize = leftInfo.maxSubBstSize;
                subBSTHead = leftInfo.subBSTHead;
            }
        }

        return new Info(min, max, allSize, maxSubBstSize, subBSTHead);
    }

    /**
     * @return boolean 判断是否不为null
     * @Author hels
     * @Date 2022/11/24 16:30
     */
    public static boolean isInfoNN(Info info) {
        return info != null;
    }


    public static class Info {
        public int min;
        public int max;
        public int allSize;
        public int maxSubBstSize;
        public Nodea subBSTHead;

        public Info(int min, int max, int allSize, int maxSubBstSize, Nodea subBSTHead) {
            this.min = min;
            this.max = max;
            this.allSize = allSize;
            this.maxSubBstSize = maxSubBstSize;
            this.subBSTHead = subBSTHead;
        }
    }
}
